import random
from typing import Tuple


def merge_sort(nums):
    if not nums or len(nums) == 0:
        return
    process(nums, 0, len(nums) - 1)

def process(nums, l, r):
    def merge(l, m, r):
        help = [0] * (r - l + 1)
        i, j, k = l, m + 1, 0
        while i <= m and j <= r:
            if nums[i] <= nums[j]:
                help[k] = nums[i]
                i += 1
            else:
                help[k] = nums[j]
                j += 1
            k += 1
        help[k:] = nums[i:m+1] if i <= m else nums[j:r+1]
        nums[l:r+1] = help[:]

    if l == r: return
    m = (l + r) // 2
    process(nums, l, m)
    process(nums, m + 1, r)
    merge(l, m, r)

# 非递归版本的merge_sort, 控制步长为2^n即1, 2, 4, 8, 16, ...
# 每次遍历数组，nums[l: l+step] 与 nums[l+step: l+step+step] 进行归并
def merge(nums, l, m, r):
    help = [0] * (r - l + 1)
    i, j, k = l, m + 1, 0
    while i <= m and j <= r:
        if nums[i] <= nums[j]:
            help[k] = nums[i]
            i += 1
        else:
            help[k] = nums[j]
            j += 1
        k += 1
    help[k:] = nums[i:m+1] if i <= m else nums[j:r+1]
    nums[l:r+1] = help[:]

def merge_sort2(nums):
    if not nums or len(nums) == 0: return
    n = len(nums)
    step = 1
    while step <= n:
        l = 0
        while l < n:
            # r = l + 2 * step - 1 if l + 2 * step - 1 < n else n - 1
            r = min(l + 2 * step - 1, n-1)
            m = l + step - 1
            # print(f'l: {l}, m: {m}, r: {r}')
            merge(nums, l, m, r)
            l = r + 1
        step *= 2


def test(n: int, ranges: Tuple[int, int], t: int):
    '''
    测试函数
    :param n: 测试数组长度
    :param maximum: 生成数组元素的大小范围
    :param t: 测试轮数
    '''
    for _ in range(t):
        arr1 = [random.randint(ranges[0], ranges[1]) for _ in range(n)]
        arr2 = arr1[:]
        arr3 = arr1[:]
        merge_sort2(arr2)
        arr3.sort()
        passed = arr2 == arr3
        if not passed:
            print('error!!!')
            print(arr1)
            print(arr2)
            print(arr3)


if __name__ == '__main__':
    print("测试开始")
    test(1000, (-1000, 1000), 100)
    print("测试结束")
